package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;

import java.util.Arrays;

/**
 * 大佬写的, 两遍.
 * 先用一次二分, 找到breakPoint, 然后就知道在breakpoint左边还是右边, 就再进行一次普通二分
 * https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/14425/Concise-O(log-N)-Binary-search-solution
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC33_2 implements DivideConquer {
    public int search(int[] nums, int target) {
        int minIdx = findMinIdx(nums);
        if (target == nums[minIdx]) return minIdx;
        int m = nums.length;
        int start = (target <= nums[m - 1]) ? minIdx : 0;
        int end = (target > nums[m - 1]) ? minIdx : m - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) return mid;
            else if (target > nums[mid]) start = mid + 1;
            else end = mid - 1;
        }
        return -1;
    }

    public int findMinIdx(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            //正常排序数组, mid一定比end小的, 如果>, 则说明breakPoint在mid和end之间!!
            if (nums[mid] > nums[end]) start = mid + 1;
            else end = mid;
        }
        return start;
    }

    public static void main(String[] args) {
    }
}
